package Javafoundation;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

public class Gragh {
    private Map<String, List<String>> graphMap=new HashMap<String, List<String>>();
    public void  initGraph() {
        graphMap.put("1",Arrays.asList("2","3"));
        graphMap.put("2",Arrays.asList("1","4","5"));
        graphMap.put("3",Arrays.asList("1","6","7"));
        graphMap.put("4",Arrays.asList("2","8"));
        graphMap.put("5",Arrays.asList("2","8"));
        graphMap.put("6",Arrays.asList("3","8","9"));
        graphMap.put("7",Arrays.asList("3","9"));
        graphMap.put("8",Arrays.asList("4","5","6"));
        graphMap.put("9",Arrays.asList("6","7"));
    }
    private Map<String, Boolean> status=new HashMap<String,Boolean>();
    private Queue<String> queue =new LinkedList<String>();
    public void BreadthFS(String startPoint) {
        queue.offer(startPoint);
        status.put(startPoint, true);
        while(!queue.isEmpty()) {
            String tempPoint =queue.poll();
            System.out.print(tempPoint+"-");
            status.put(tempPoint, false);
            for (String point : graphMap.get(tempPoint)) {
                if(status.getOrDefault(point, true)){
                    if(!queue.contains(point)) {
                        queue.offer(point);
                    }
                }
            } }
    }
    public void depthFS(String startPoint) {
        Stack<String> stack=new Stack<String>();
        Map<String, Boolean> status=new HashMap<String,Boolean>();
        stack.push(startPoint);
        while (!stack.isEmpty()) {
            System.out.print("\t");
            for (String string : stack) {
                System.out.print(string);
                if(!string.equals(stack.lastElement())){
                    System.out.print("->");
                }
            }
            System.out.println();

            String tempPoint =stack.pop();

            status.put(tempPoint, false);
            System.out.print(tempPoint);
            for (String point : graphMap.get(tempPoint)) {
                if(status.getOrDefault(point, true)) {

                    if(!stack.contains(point)) {
                        stack.push(point);
                    }else {
                        stack.remove(point);
                        stack.push(point);
                    }
                }
            }
        }
    }
    //无向图的深度优先遍历
    public void depthFSwithRecusive(String StartPoint) {
        if(status.getOrDefault(StartPoint,true)) {
            System.out.print(StartPoint+"-");
            status.put(StartPoint, false);
        }
        for (String point : graphMap.get(StartPoint)) {
            if(status.getOrDefault(point,true)) {
                depthFSwithRecusive(point);
            }
        }
    }
}
